{
LANG : PASCAL
PROB : inflate
}

program INFLATE;
const
  fi = 'inflate.in';
  fo = 'inflate.out';
  max = 10000;
var
  d : array[0..max] of longint;
  n, m : longint;

procedure process;
var
  i, j, u, v : longint;
begin
  fillchar(d, sizeof(d), 0);
  d[0] := 0;
  for i := 1 to n do
  begin
    read(u, v);
    for j := v to m do
      if d[j] < d[j-v] + u then d[j] := d[j-v] + u;
  end;
end;

begin
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);
  read(m, n);
  process;
  writeln(d[m]);
  close(output);
  close(input);
end.